package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type Node struct {
	treeNode *TreeNode
	depth    int
}

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	result := [][]int{}
	queue := []*Node{
		{treeNode: root, depth: 0},
	}
	for len(queue) > 0 {
		head := queue[0]
		queue = queue[1:]
		if head != nil && head.treeNode != nil {
			// put into result
			level := head.depth
			if level == len(result) {
				result = append(result, make([]int, 0))
			}
			result[level] = append(result[level], head.treeNode.Val)

			// put children in queue
			queue = append(queue, &Node{treeNode: head.treeNode.Left, depth: head.depth + 1})
			queue = append(queue, &Node{treeNode: head.treeNode.Right, depth: head.depth + 1})
		}
	}
	return result
}

func main() {
	root := &TreeNode{Val: 3}
	n1 := &TreeNode{Val: 9}
	n2 := &TreeNode{Val: 20}
	n3 := &TreeNode{Val: 15}
	n4 := &TreeNode{Val: 7}
	root.Left = n1
	root.Right = n2
	n2.Left = n3
	n2.Right = n4
	println(levelOrder(root))
}
